package cn.z2huo.algorithm.query.half;

/**
 * <p>折半查找
 * <p>前提是所列举的数组是已经排好序的
 *
 * @author z2huo
 */
public class HalfQuery {

    /**
     * 折半查找
     *
     * @param array   待查找正序数组
     * @param element 待查找元素
     * @return 待查找元素在正序数组中的位置
     */
    public int query(int[] array, int element) {
        if (array == null || array.length == 0) {
            return -1;
        }

        int result = -1;
        int idxLow, idxHigh, idxMid;

        idxLow = 0;
        idxHigh = array.length - 1;
        idxMid = (idxLow + idxHigh) / 2;

        for (; idxLow <= idxHigh; idxMid = (idxLow + idxHigh) / 2) {
            if (element < array[idxMid]) {
                idxHigh = idxMid - 1;
            } else if (element > array[idxMid]) {
                idxLow = idxMid + 1;
            } else {
                result = idxMid;
                break;
            }
        }

        return result;
    }

    @Deprecated
    public static void main(String[] args) {
        int low, mid, high;
        int flag = 88;
        int demo = 0;
//		int[] array = {5,13,19,21,37,56,64,75,80,88,92};
        int[] array = {5, 13, 19, 21, 37, 40, 56, 64, 75, 80, 88, 92};

        low = 0;
        high = array.length - 1;
        mid = (low + high) / 2;
        while (low <= high) {
            //当要查找的数比中小时
            if (flag < array[mid]) {
                high = mid - 1;
                mid = (low + high) / 2;
                demo++;
            } else if (flag > array[mid]) {
                //当要查找的数比中大时
                low = mid + 1;
                mid = (low + high) / 2;
                demo++;
            } else if (flag == array[mid]) {
                //当要查找的数和中相等时，退出，得到结果
                demo++;
                System.out.println("进行了" + demo + "次比较！");
                System.out.println("要查找的元素在数组中的：" + mid + "位置！");
                break;
            }
        }
    }
}
